package middle;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class CopyListWithRandomPointer {
    /**
     * 该题的难点在于，我们在遍历复制链表时，随机指针指向的结点，有可能未进行初始化，有可能已经进行了初始化，我们无法直接赋值随机指针的指向。
     *
     * 该题的思路在于在遍历链表过程中，用hashMap存储复制的结点和原结点（其包含了随机指针指向的结点）
     * 然后第二次遍历，将复制的新链表的每个结点的随机指针进行赋值。
     * */
    class Solution {
        public Node copyRandomList(Node head) {
            if(head == null){
                return null;
            }
            HashMap<Node, Node> map = new HashMap<>();
            Node curNode = head;
            // 第一次遍历，复制链表的每个结点
            while(curNode != null){
                map.put(curNode, new Node(curNode.val));
                curNode = curNode.next;
            }
            curNode = head;
            // 第二次遍历， 给复制的每个结点赋值random指针
            while(curNode != null){
                Node node = map.get(curNode);
                node.next = map.get(curNode.next);
                node.random = map.get(curNode.random);
                curNode = curNode.next;
            }
            return map.get(head);
        }
    }

    /**
     * 使用递归+回溯的方式
     * 实际上 思路和第一种方法是一样的。
     * */
    class Solution1 {
        Map<Node, Node> map = new HashMap<>();
        public Node copyRandomList(Node head) {
           if(head == null){
               return null;
           }
           if(!map.containsKey(head)){
               Node node = new Node(head.val);
               map.put(head,node);
               node.next = copyRandomList(head.next);
               node.random = map.get(head.random);
           }
           return map.get(head);
        }
    }


    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
